package com.formula.datastructure.exam.sort;

import com.formula.datastructure.util.DataUtil;

public class QuickSort {
    public Integer[] sort(Integer[] array) {
        quicksort(array, 0, array.length - 1);
        return array;
    }

    void quicksort(Integer[] array, int origLow, int origHigh) {

        if (origLow < origHigh) {
            int low = origLow;
            int high = origHigh;
            Integer pivot = array[low];

            while (low < high) {
                while (low < high && pivot <= array[high]) {
                    high--;
                }
                array[low] = array[high];

                while (low < high && pivot > array[low]) {
                    low++;
                }
                array[high] = array[low];
            }

            array[low] = pivot;

            quicksort(array, origLow, low - 1);
            quicksort(array, low + 1, origHigh);
        }
    }

    public static void main(String[] args) {
        QuickSort quick = new QuickSort();

        int size = 20;
        int range = 999;
        Integer[] array = DataUtil.genUniqueArray(size, range);
        DataUtil.printIndex(size);
        DataUtil.printArray(array);
        DataUtil.printArray(quick.sort(array));
    }
}
